﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0034_Rotate : IAlgorithm
    {
        // 189. 轮转数组

        // 给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

        // 提示：
        //    1 <= nums.length <= 10^5
        //    -2^31 <= nums[i] <= 2^31 - 1
        //    0 <= k <= 10^5

        // 进阶：
        //   尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
        //   你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 0, 1, 2, 3, 4, 5, 6 };
            int k = 3;
            // 算法执行与打印
            Rotate(nums, k);
            foreach (var item in nums)
            {
                Console.WriteLine(item);
            }
        }

        // 算法
        public void Rotate(int[] nums, int k)
        {
            if (nums.Length == 1 || k == 0)
                return;
            int count = 0, s = 0, i = k % nums.Length;
            bool start = false;
            while (count < nums.Length)
            {
                var temp = nums[s];
                while (count < nums.Length && (!start || (start && (s + k) % nums.Length != i)))
                {
                    start = true;
                    var innerTemp = nums[i];
                    nums[i] = temp;
                    temp = innerTemp;
                    i = (i + k) % nums.Length;
                    count++;
                }
                s++;
                i = (s + k) % nums.Length;
                start = false;
            }
        }

        //双重循环
        //时间复杂度：O(kn)
        //空间复杂度：O(1)       
        public void Rotate1(int[] nums, int k)
        {
            int n = nums.Length;
            k %= n;
            for (int i = 0; i < k; i++)
            {
                int temp = nums[n - 1];
                for (int j = n - 1; j > 0; j--)
                {
                    nums[j] = nums[j - 1];
                }
                nums[0] = temp;
            }
        }

        //翻转
        //时间复杂度：O(n)
        //空间复杂度：O(1)
        public void Rotate2(int[] nums, int k)
        {
            int n = nums.Length;
            k %= n;
            Reverse(nums, 0, n - 1);
            Reverse(nums, 0, k - 1);
            Reverse(nums, k, n - 1);
        }
        private void Reverse(int[] nums, int start, int end)
        {
            while (start < end)
            {
                int temp = nums[start];
                nums[start++] = nums[end];
                nums[end--] = temp;
            }
        }

        /**
         * 循环交换
         * 时间复杂度：O(n)
         * 空间复杂度：O(1)
         */
        public void Rotate3(int[] nums, int k)
        {
            int n = nums.Length;
            k %= n;
            // 第一次交换完毕后，前 k 位数字位置正确，后 n-k 位数字中最后 k 位数字顺序错误，继续交换
            for (int start = 0; start < nums.Length && k != 0; n -= k, start += k, k %= n)
            {
                for (int i = 0; i < k; i++)
                {
                    Swap(nums, start + i, nums.Length - k + i);
                }
            }
        }
        private void Swap(int[] nums, int i, int j)
        {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}
